package com.acwing.partition13;

import java.io.*;
import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2022/3/7 10:17
 */
public class AC1217垒骰子_矩阵快速幂 {

    private static final int N = 6, MOD = 1000000007;
    private static final int[] dict = {3, 4, 5, 0, 1, 2};
    private static long[][] a = new long[N][N];
    private static int n, m;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        for (int i = 0; i < N; i++) Arrays.fill(a[i], 4);
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int x = Integer.parseInt(ss[0]) - 1, y = Integer.parseInt(ss[1]) - 1;
            a[dict[x]][y] = a[dict[y]][x] = 0;
        }
        long[][] res = qmi(a, n - 1), f = new long[][]{{4, 4, 4, 4, 4, 4}};
        res = mul(f, res);
        long ans = 0;
        for (int i = 0; i < N; i++) ans = (ans + res[0][i]) % MOD;
        writer.write(ans + "\n");
        writer.flush();
    }

    private static long[][] qmi(long[][] mat, int k) {
        //初始化单位矩阵
        long[][] res = new long[mat.length][mat[0].length];
        for (int i = 0; i < res.length; i++) res[i][i] = 1;
        while (k != 0) {
            if ((k & 1) == 1) res = mul(res, mat);
            k >>= 1;
            mat = mul(mat, mat);
        }
        return res;
    }

    private static long[][] mul(long[][] m1, long[][] m2) {
        long[][] m3 = new long[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m1[0].length; k++) {
                    m3[i][j] = (m3[i][j] + m1[i][k] * m2[k][j] % MOD) % MOD;
                }
            }
        }
        return m3;
    }
}
